// https://leetcode.cn/problems/search-a-2d-matrix-ii/submissions/

// 法一：每行二分查找
class Solution {
public:
    int binarySearch(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) start = mid;
            else end = mid;
        }
        if (nums[start] == target) return start;
        if (nums[end] == target) return end;
        return -1;
    }
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) return false;
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] > target) break;
            if (matrix[i][n - 1] < target) continue;
            int res = binarySearch(matrix[i], target);
            if (res != -1) return true;
        }
        return false;
    }
};

// 法二：双指针
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int x = m - 1;
        int y = 0;
        while (x >= 0 && y < n) {
            if (matrix[x][y] == target) return true;
            if (matrix[x][y] < target) ++y;
            else --x;
        }
        return false;
    }
};

// 法三：二分区间
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int l = matrix[0][0];
        int r = matrix[m - 1][n - 1];
        if (l == target || r == target) return true; //注意
        while (l + 1 < r) {
            int mid = (r - l) / 2 + l;
            int i = m - 1;
            int j = 0;
            while (i >= 0 && j < n) {
                if (matrix[i][j] == target) return true;
                if (matrix[i][j] < mid) j++;
                else i--;
            }
            if (mid < target) l = mid;
            else r = mid;
        }
        return false;
    }
};

// 法四：BFS (TLE)
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        queue<pair<int, int>> q;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<bool>> visited(m ,vector<bool>(n, false));
        q.emplace(0, 0);
        visited[0][0] = true;
        vector<int> dx = {0, 1};
        vector<int> dy = {1, 0};
        while (!q.empty()) {
            int x, y;
            tie(x, y) = q.front();
            q.pop();
            if (matrix[x][y] == target) return true;
            for (int i = 0; i < dx.size(); ++i) {
                int newx = x + dx[i];
                int newy = y + dy[i];
                if (newx >= 0 && newx < m && newy >= 0 && newy < n && !visited[newx][newy]) {
                    q.emplace(newx, newy);
                    visited[newx][newy] = true;
                }
                
            }
        } 
        return false;
    }
};
